package exam.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
        test.addMinimum("abcbcabc");
    }


    public int[] rowAndMaximumOnes(int[][] mat) {

        int m = mat.length;
        int n = mat[0].length;

        int[] ans = new int[2];

        for(int i = 0;i<m;i++){
            int count = 0;  //1的个数
            for(int j = 0;j<n;j++){
                if(mat[i][j] == 1){
                    count++;
                }
            }
            if(count > ans[1]){
                ans[0] = i;
                ans[1] = count;
            }
        }
        return ans;
    }

    public int maxDivScore(int[] nums, int[] divisors) {
        int maxScore = -1;
        int maxDivisor = Integer.MAX_VALUE;
        for (int divisor : divisors) {
            int score = 0;
            for (int num : nums) {
                if (num % divisor == 0) {
                    score++;
                }
            }
            if (score > maxScore) {
                maxScore = score;
                maxDivisor = divisor;
            } else if (score == maxScore) {
                maxDivisor = Math.min(maxDivisor, divisor);
            }
        }
        return maxDivisor;
    }

    public int addMinimum(String word) {
        int ans = 0;

        String[] words = word.split("abc");

        for(String str : words){
            int n = str.length();

            for (int i = 0;i<n;){
                if(i<n && str.charAt(i) == 'a' && str.charAt(i+1) != 'b'){
                    ans += 2;
                    i+=2;
                }else if(i<n && str.charAt(i) == 'a' && (str.charAt(i+1) == 'b' || str.charAt(i+1) == 'c')){
                    ans += 1;
                    i++;
                }else if(i<n && str.charAt(i) == 'b' && str.charAt(i+1) != 'c'){
                    ans += 2;
                    i+=2;
                }else if(i<n && str.charAt(i) == 'b' && str.charAt(i+1) =='c'){
                    ans += 1;
                    i++;
                }
            }
        }
        return ans;
    }

    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        int len = price.length;
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < len; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            adj[u].add(v);
            adj[v].add(u);
        }
        int[][] f = new int[n][2];
//        dfs(adj, f, price, 0, -1);
        int ans = 0;
        for (int[] trip : trips) {
            int start = trip[0], end = trip[1];
            int sum = Integer.MAX_VALUE;
            for (int i = 0; i < 2; i++) {
                sum = Math.min(sum, f[start][i] + dfs(adj, f, price, end, start, i));
            }
            ans += sum;
        }
        return ans;
    }
    private int dfs(List<Integer>[] adj, int[][] f, int[] price, int u, int p, int s) {
        if (f[u][s] != 0) {
            return f[u][s];
        }
        int sum = 0;
        for (int v : adj[u]) {
            if (v != p) {
                if (s == 0) {
                    sum += dfs(adj, f, price, v, u, 1);
                } else {
                    sum += Math.min(dfs(adj, f, price, v, u, 0), dfs(adj, f, price, v, u, 1));
                }
            }
        }
        if (s == 0) {
            sum += price[u];
            f[u][s] = sum;
        } else {
            sum += price[u] / 2;
            f[u][s] = sum;
        }
        return sum;
    }
}
